// https://www.lintcode.com/problem/friend-circles/description

// 法一：并查集
// class UnionFind {
//     public:
//         int* father;
//         int count;
        
//     UnionFind(int n)
//     {
//         father = new int[n];
//         for (int i = 0; i < n; ++i)
//         {
//             father[i] = i;
//         }
//         count = n;
//     }
//     int find(int n)
//     {
//         if (father[n] == n)
//             return n;
//         else
//             // return father[n] = find(n);
//             return father[n] = find(father[n]);
//     }
//     void connect(int a, int b)
//     {
//         int fatherA = find(a);
//         int fatherB = find(b);
//         if (fatherA != fatherB)
//         {
//             father[fatherA] = fatherB;
//             count--;
//         }
//     }
//     int check()
//     {
//         return count;
//     }
// }; //别忘了

// class Solution {
// public:
//     /**
//      * @param M: a matrix
//      * @return: the total number of friend circles among all the students
//      */
//     int findCircleNum(vector<vector<int>> &M) {
//         int n = M.size();
//         UnionFind uf(n);
//         for (int i = 0; i < n; ++i)
//         {
//             for (int j = 0; j < n; ++j)
//             {
//                 if (M[i][j] == 1)
//                 {
//                     uf.connect(i, j);
//                 }
//             }
//         }
//         return uf.check();
//     }
// };



// 法二：BFS
// 本题在于考察基本的联通块计数问题，搜索可行，也可以用并查集。题解采用bfs，如果当前对角线位置为1，开始bfs，如果为2，表示这个人已经搜索统计过了。
// bfs中的i循环是为了控制当前搜索的点到起点距离相同，j取出队列首个元素，然后k是遍历朋友关系。
// 如果对角线为1，说明当前这个人位于一个新的联通块内，count++
// class Solution {
// public:
//     void BFS(int student,vector<vector<int>> &M) {   
//         queue<int> q;
//         q.push(student);
//         while (!q.empty()) {
//             int size = q.size();
//             for (int i = 0; i < size; i++) {    //控制每轮搜索的点到起点的距离相同
//                 int j = q.front();
//                 q.pop();
//                 M[j][j] = 2; 
//                 for (int k = 0; k < M[0].size(); k++) {	//遍历朋友关系
//                     if (M[j][k] == 1 && M[k][k] == 1) {   //如果M[k][k]==1，说明k没被遍历，需要继续搜索  
//                         q.push(k);  
//                     }
//                 }
//             }
//         }
//     }
//     int findCircleNum(vector<vector<int>> &M) {
//         // Write your code here
//         int count = 0;
//         for (int i = 0; i < M.size(); i++) {
//             if (M[i][i] == 1) {    //如果当前对角线为1，说明这个人位于新的联通块内
//                 count++; 			//计数+1
//                 BFS(i, M);			//开始搜索
//             }
//         }
//         return count;
//     }
// };

// 法三：DFS
class Solution {
public:
    void DFS(vector<vector<int>> &M, int i) {
        if (M[i][i] == 1)
        {
            M[i][i] = 2;
            for (int j = 0; j < M[0].size(); ++j)
            {
                if (j != i && M[i][j] == 1)
                    DFS(M, j);
            }
        }
    }
    int findCircleNum(vector<vector<int>> &M) {
        int count = 0;
        for (int i = 0; i < M.size(); ++i)
        {
            if (M[i][i] == 1)
            {
                DFS(M, i);
                count++;
            }
        }
        return count;
    }
};